/**
 * Created with IntelliJ IDEA.
 * Description:双指针算法
 * User: LianBao
 * Date: 2024-04-25
 * Time: 22:31
 */
public class DoublePointer {

    /**
     * 1.移动零
     * https://leetcode.cn/problems/move-zeroes/description/
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int dest = -1;//
        for (int cur = 0; cur < nums.length; cur++) {
            if (nums[cur] != 0) {
                dest++;
                int tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
            }
        }
    }


    /**
     * 2.复写零
     * https://leetcode.cn/problems/duplicate-zeros/
     * @param arr
     */
    /**
     * 1.找到最后一个要复写的数-->双指针
     * 2.从后往前完成复写操作
     */
    public void duplicateZeros(int[] arr) {
        //1.利用双指针算法,找到最后一个复写的数
        //1.1 先判断cur位置的值
        //1.2 决定dest向后移动一步或者两步
        //1.3 判断dest位置的合法性
        //1.4 cur++
        //此时dest正好是最后一个元素的位,cur正好是最后一个复写的数

        int dest = -1;//数组的最后一个元素的位置
        int cur = 0;//最后一个复写的数的位置
        while (cur < arr.length) {
            if (arr[cur] != 0) {
                dest++;
            } else {
                dest += 2;
            }
            if (dest >= arr.length - 1) {
                break;
            }
            cur++;
        }

        //2.处理边界情况
        //特例:1,0,2,3,0,4
        if (dest == arr.length) {
            arr[arr.length - 1] = 0;
            dest -= 2;
            cur--;
        }

        //3.从后往前复写
        while (cur >= 0) {
            if (arr[cur] != 0) {
                arr[dest] = arr[cur];
                dest--;
                cur--;
//                arr[dest--] = arr[cur--];
            } else {
                arr[dest] = 0;
                dest--;
                arr[dest] = 0;
                dest--;
/*                arr[dest--] = 0;
                arr[dest--] = 0;*/
                cur--;
            }
        }
    }


}
